/*
 * @lc app=leetcode.cn id=939 lang=cpp
 *
 * [939] 最小面积矩形
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int minAreaRect(vector<vector<int>> &points)
    {
        int ans = INT_MAX;

        sort(points.begin(), points.end());

        for (int i = 0; i < points.size(); i++)
        {
            const auto &p1 = points[i];
            int last_height = INT_MAX;
            auto last_p1 = p1;
            for (int j = i + 1; j < points.size(); j++)
            {
                const auto &p2 = points[j];
                if (p1[0] != p2[0]) //即使两个点在横轴上共线也不可能构成举行
                    break;          //升序排列，所以之后不可能有满足条件的两个点了

                if (p2[1] - p1[1] >= ans) //高大于已有的面积退出即可
                {
                    break;
                }

                //因为点是按坐标升序排列的
                //保证p1[0] == p2[0] 才有可能后续组成矩形
                int k = j + 1;
                while (k < points.size() && points[k][0] == p1[0])
                    k++;
                const int max_with = ans / (p2[1] - p1[1]);
                for (; k < points.size(); k++)
                {
                    //此时一定有p1[0] == p2[0]
                    /**
                     * p2
                     * p1
                     */
                    const auto &p3 = points[k];
                    if (p3[0] - p1[0] > max_with)
                        break;
                    if (p3[1] == p1[1] && p3[0] != p1[0])
                    {
                        /**
                         * 此时有
                         * p2
                         *
                         * p1    p3
                         */
                        int x = p3[0], y = p2[1], area = abs(p3[0] - p1[0]) * abs(p2[1] - p1[1]);
                        if (area >= ans)
                            break;

                        for (int h = k + 1; h < points.size() && x == points[h][0] && y >= points[h][1]; h++)
                        {
                            if (y == points[h][1])
                            {
                                ans = area;
                                break;
                            }
                        }
                    }
                }
            }
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

// int main()
// {
//     vector<vector<int>> v = {{13693, 7537}, {27094, 9745}, {13693, 1567}, {27094, 17491}, {27094, 14208}, {13693, 27238}, {13693, 11153}, {27094, 12919}, {13693, 36766}, {13693, 32490}, {13693, 31447}, {27094, 7485}, {27094, 36444}, {13693, 14020}, {27094, 5649}, {13693, 15484}, {13693, 26023}, {13693, 35101}, {27094, 33165}, {27094, 4378}, {13693, 20855}, {13693, 22011}, {13693, 33991}, {13693, 37503}, {13693, 31051}, {13693, 25357}, {13693, 5859}, {13693, 16985}, {27094, 38666}, {27094, 37827}, {13693, 17255}, {13693, 10399}, {27094, 37149}, {13693, 7427}, {27094, 5376}, {13693, 31974}, {13693, 5649}, {27094, 36792}, {13693, 17697}, {13693, 21022}, {27094, 21929}, {13693, 17600}, {27094, 18304}, {13693, 25208}, {27094, 1791}, {27094, 15134}, {13693, 21681}, {27094, 9997}, {13693, 36011}, {27094, 23236}, {13693, 26477}, {13693, 12260}, {13693, 2906}, {13693, 13265}, {13693, 2621}, {27094, 23835}, {27094, 27280}, {13693, 31104}, {13693, 36214}, {27094, 862}, {27094, 4576}, {27094, 19550}, {27094, 24756}, {27094, 8569}, {27094, 30167}, {27094, 39832}, {13693, 31188}, {27094, 36751}, {27094, 9890}, {27094, 9960}, {13693, 13796}, {27094, 5826}, {13693, 7881}, {27094, 38277}, {27094, 18}, {27094, 31974}, {27094, 13439}, {27094, 213}, {13693, 35338}, {13693, 13792}, {27094, 11155}, {27094, 23005}, {27094, 31349}, {27094, 20542}, {27094, 5859}, {27094, 3220}, {13693, 9960}, {13693, 8211}, {27094, 18587}, {27094, 23694}, {27094, 4521}, {27094, 22098}, {13693, 5826}, {13693, 39092}, {27094, 20113}, {27094, 19273}, {27094, 18274}, {27094, 22439}, {13693, 18304}, {13693, 14552}, {13693, 7246}, {13693, 37530}, {27094, 17589}, {13693, 37149}, {13693, 27110}, {27094, 31188}, {27094, 37623}, {13693, 26398}, {27094, 27238}, {27094, 22571}, {13693, 36751}, {27094, 8608}, {27094, 12601}, {27094, 28342}, {27094, 24443}, {27094, 13265}, {27094, 20420}, {27094, 32006}, {27094, 15095}, {13693, 1252}, {13693, 22182}, {27094, 31252}, {27094, 7537}, {13693, 39115}, {13693, 32236}, {27094, 9382}, {13693, 9890}, {27094, 20830}, {27094, 19892}, {27094, 633}, {27094, 33211}, {27094, 16203}, {27094, 7881}, {13693, 29671}, {27094, 39031}, {27094, 36032}, {27094, 34291}, {27094, 33991}, {27094, 27110}, {27094, 39295}, {13693, 22439}, {27094, 8664}, {13693, 20542}, {13693, 38666}, {13693, 8664}, {27094, 39346}, {27094, 31051}, {13693, 32612}, {27094, 30581}, {13693, 30715}, {27094, 21834}, {27094, 20438}, {13693, 13439}, {27094, 28527}, {13693, 24832}, {27094, 1252}, {13693, 34180}, {27094, 37823}, {13693, 497}, {27094, 32236}, {27094, 11153}, {13693, 25802}, {13693, 13078}, {27094, 36637}, {13693, 27797}, {13693, 37302}, {13693, 38334}, {13693, 4078}, {13693, 32006}, {13693, 38577}, {27094, 12857}, {27094, 26850}, {27094, 37530}, {27094, 33264}, {27094, 10333}, {13693, 25795}, {13693, 14820}, {13693, 1791}, {27094, 28267}, {27094, 11669}, {13693, 18587}, {27094, 20483}, {13693, 25437}, {13693, 4521}, {13693, 37827}, {13693, 37823}, {27094, 39654}, {27094, 37503}, {27094, 23130}, {13693, 4680}, {27094, 30715}, {13693, 28971}, {13693, 39031}, {27094, 17255}, {13693, 12857}, {27094, 23488}, {13693, 39600}, {13693, 4177}, {13693, 19550}, {13693, 39295}, {27094, 14820}, {13693, 33113}, {27094, 35101}, {13693, 30292}, {27094, 4879}, {13693, 32491}, {27094, 6539}, {13693, 18274}, {27094, 6837}, {13693, 33211}, {27094, 26477}, {13693, 35678}, {13693, 18538}, {13693, 23488}, {13693, 32011}, {13693, 28342}, {27094, 15915}, {27094, 21022}, {27094, 10041}, {13693, 9745}, {27094, 22993}, {13693, 7818}, {27094, 21232}, {13693, 37623}, {27094, 36583}, {13693, 6926}, {13693, 23130}, {27094, 38334}, {27094, 32612}, {13693, 4375}, {13693, 21834}, {13693, 4526}, {27094, 32138}, {13693, 33018}, {13693, 18413}, {27094, 7427}, {13693, 10333}, {27094, 26555}, {27094, 31249}, {13693, 12651}, {13693, 7360}, {27094, 30621}, {13693, 633}, {13693, 21232}, {27094, 9982}, {13693, 20369}, {13693, 26983}, {13693, 20671}, {13693, 20363}, {13693, 21676}, {27094, 21191}, {13693, 14925}, {13693, 3950}, {13693, 23236}, {13693, 31759}, {27094, 4375}, {13693, 6837}, {13693, 11488}, {13693, 15915}, {27094, 5223}, {27094, 14155}, {13693, 10041}, {27094, 18538}, {27094, 1567}, {27094, 17600}, {13693, 20830}, {27094, 25967}, {27094, 24462}, {13693, 9997}, {27094, 32491}, {13693, 27633}, {13693, 16231}, {13693, 24443}, {27094, 31121}, {27094, 31759}, {27094, 39600}, {13693, 8608}, {27094, 34180}, {13693, 25698}, {13693, 7597}, {13693, 27470}, {13693, 30244}, {27094, 24832}, {13693, 31249}, {27094, 14146}, {13693, 31400}, {27094, 13796}, {27094, 18773}, {27094, 26398}, {13693, 22098}, {13693, 30621}, {27094, 25357}, {27094, 37302}, {27094, 37018}, {27094, 8211}, {27094, 14020}, {27094, 29671}, {13693, 1731}, {13693, 27771}, {13693, 28927}, {13693, 6091}, {13693, 33165}, {27094, 19431}, {27094, 7818}, {27094, 13792}, {13693, 13737}, {27094, 7360}, {13693, 28267}, {13693, 6539}, {27094, 17697}, {27094, 30292}, {13693, 20487}, {13693, 39346}, {27094, 14317}, {27094, 38577}, {13693, 1282}, {27094, 2621}, {13693, 20420}, {13693, 15034}, {13693, 2139}, {27094, 25698}, {27094, 14552}, {13693, 34291}, {27094, 22011}, {27094, 4177}, {13693, 4576}, {13693, 30581}, {13693, 12919}, {27094, 4455}, {27094, 33113}, {27094, 25208}, {27094, 27633}, {13693, 10240}, {27094, 12260}, {27094, 13737}, {27094, 20487}, {27094, 26023}, {13693, 38020}, {13693, 23835}, {13693, 5223}, {27094, 21453}, {27094, 2906}, {27094, 27559}, {13693, 25967}, {13693, 8989}, {27094, 9642}, {13693, 32680}, {27094, 13078}, {13693, 15134}, {13693, 34690}, {13693, 17722}, {27094, 1731}, {27094, 3950}, {13693, 20438}, {27094, 31400}, {27094, 25437}, {27094, 39174}, {27094, 6091}, {27094, 15484}, {13693, 38277}, {13693, 18773}, {13693, 19273}, {27094, 12651}, {27094, 27797}, {13693, 36583}, {13693, 18}, {13693, 19336}, {27094, 39092}, {13693, 27679}, {27094, 4526}, {13693, 4378}, {27094, 31104}, {13693, 31121}, {13693, 17491}, {27094, 31447}, {27094, 27470}, {13693, 23984}, {27094, 25802}, {27094, 36766}, {13693, 27559}, {13693, 36637}, {27094, 21676}, {13693, 17589}, {13693, 22571}, {13693, 24462}, {13693, 12601}, {27094, 27679}, {27094, 16985}, {13693, 21191}, {13693, 33906}, {13693, 862}, {27094, 15034}, {13693, 5376}, {13693, 16203}, {27094, 12851}, {27094, 14747}, {13693, 4455}, {27094, 36214}, {27094, 39739}, {13693, 9642}, {27094, 20369}, {13693, 31349}, {27094, 8989}, {27094, 20363}, {27094, 39996}, {13693, 14155}, {13693, 39654}, {13693, 36444}, {13693, 13631}, {27094, 28971}, {27094, 28927}, {13693, 39174}, {27094, 27771}, {13693, 31252}, {13693, 32138}, {27094, 32680}, {27094, 39115}, {13693, 1508}, {13693, 22993}, {27094, 34690}, {27094, 18413}, {13693, 11155}, {13693, 19934}, {13693, 24756}, {13693, 14208}, {27094, 6926}, {13693, 15095}, {13693, 26555}, {27094, 13631}, {27094, 23520}, {13693, 19431}, {27094, 14925}, {13693, 12851}, {13693, 21929}, {13693, 33729}, {27094, 33906}, {13693, 26850}, {27094, 32413}, {27094, 32011}, {13693, 8569}, {13693, 33264}, {13693, 39739}, {13693, 20113}, {27094, 20855}, {27094, 2139}, {27094, 10399}, {27094, 21681}, {27094, 7246}, {13693, 30167}, {27094, 19336}, {27094, 36011}, {13693, 4879}, {13693, 3220}, {13693, 23520}, {27094, 4078}, {27094, 16231}, {13693, 14317}, {13693, 23694}, {27094, 1282}, {27094, 497}, {13693, 213}, {27094, 1508}, {13693, 36792}, {27094, 35338}, {27094, 20671}, {27094, 19934}, {13693, 39996}, {13693, 23005}, {13693, 9982}, {27094, 23984}, {27094, 38020}, {13693, 20483}, {13693, 28527}, {13693, 37018}, {27094, 10240}, {27094, 33018}, {13693, 11669}, {13693, 36032}, {27094, 30244}, {13693, 21453}, {13693, 27280}, {27094, 25795}, {13693, 32413}, {13693, 39832}, {27094, 32490}, {13693, 9382}, {13693, 7485}, {27094, 7597}, {13693, 19892}, {27094, 17722}, {13693, 14146}, {27094, 4680}, {27094, 22182}, {27094, 26983}, {27094, 33729}, {13693, 14747}, {27094, 11488}, {27094, 35678}};

//     // vector<vector<int>> v = {
//     //     {0, 1}, {1, 3}, {3, 3}, {4, 4}, {1, 4}, {2, 3}, {1, 0}, {3, 4}};

//     cout << Solution().minAreaRect(v) << endl; // 13401
//     return 0;
// }

// @lc code=end
